/*
 * @Date: 2024-04-20 00:49:02
 * @LastEditors: 玄绮 shijiahansi@qq.com
 * @LastEditTime: 2024-04-20 15:27:10
 * @FilePath: \BigTalkDataStructure\tools\tree\bitree.c
 */
#include "bitree.h"

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

/**
 * @brief 创建一个新的节点
 *
 * @param data
 * @return BiTreeNodt_t*
 */
inline static PBiTree_t __create_Node(BiTreeData_t data) {
    PBiTree_t newT = (BiTree_t*)malloc(sizeof(BiTree_t));
    if (newT == NULL) return NULL;

    newT->data = data;
    newT->left_child = newT->right_child = NULL;
    return newT;
}

/**
 * @brief 销毁一个节点
 *
 * @param p
 */
inline static void __distory_Node(PBiTree_t p) {
    if (p) return;
    free(p);
}
/**
 * @brief 递归查找
 *
 * @param t
 * @param data
 * @param f
 * @param p
 * @return true
 * @return false
 */
static bool bitree_find_BST(PBiTree_t t, BiTreeData_t data, PBiTree_t f, PBiTree_t* p) {
    if (t == NULL) {
        // 如果到达末尾都没有找到，p 设置为 末尾节点 的上一个节点
        *p = f;
        return false;
    }

    if (t->data == data) {
        // 如果找到了，p 设置为当前节点
        *p = t;
        return true;
    }
    else if (data < t->data) {
        // 如果 data 比当前节点小，则查找左子树
        return bitree_find_BST(t->left_child, data, t, p);
    }
    else {
        // 否则查找右子树
        return bitree_find_BST(t->right_child, data, t, p);
    }
    return false;
}

/**
 * @brief 在二叉树中查找
 *
 * @param t 查询的二叉树
 * @param data 查询的数据
 * @param p 返回查找到的节点
 * @return true 找到
 * @return false 未找到
 */
bool bitree_find(PBiTree_t t, BiTreeData_t data, PBiTree_t* p) {
    return bitree_find_BST(t, data, NULL, p);
}

/**
 * @brief 插入数据
 *
 * @param t 要插入的二叉树
 * @param data 要插入的数据
 * @return true 成功
 * @return false 已经存在，失败
 */
bool bitree_insert(PBiTree_t* t, BiTreeData_t data) {
    PBiTree_t p;
    if (!bitree_find(*t, data, &p)) {
        PBiTree_t newT = __create_Node(data);
        if (newT == NULL) return false;

        if (*t == NULL) {
            *t = newT;
        }
        else if (data < p->data) {
            p->left_child = newT;
        }
        else {
            p->right_child = newT;
        }

        return true;
    }
    return false;
}

/**
 * @brief 删除节点
 *
 * @param t
 * @return true
 * @return false
 */
static bool __delete(PBiTree_t* p) {
    PBiTree_t q, s;

    if ((*p)->right_child == NULL) {
        q = (*p);
        *p = (*p)->left_child;
        __distory_Node(q);
    }
    else if ((*p)->left_child == NULL) {
        q = (*p);
        *p = (*p)->right_child;
        __distory_Node(q);
    }
    else {
        // 左转，然后走到右侧的尽头
        q = *p, s = (*p)->left_child;
        while (s->right_child) {
            q = s;
            s = s->right_child;
        }

        (*p)->data = s->data;
        if (q != *p)
            q->right_child = s->left_child;
        else
            q->left_child = s->left_child;
    }

    return true;
}

/**
 * @brief 二叉排序树中存在 关键字 等于 data 的元素时，则删除该节点
 *
 * @param t 要操作的二叉树
 * @param data 要删除的关键字
 * @return true 成功
 * @return false 失败
 */
bool bitree_delete(PBiTree_t* t, BiTreeData_t data) {
    if (!*t) {
        // 不存在关键字等于 data 的元素
        return false;
    }

    if ((*t)->data == data) {
        return __delete(t);
    }
    else if (data < (*t)->data) {
        return bitree_delete(&(*t)->left_child, data);
    }
    else {
        return bitree_delete(&(*t)->right_child, data);
    }

    return true;
}

/**
 * @brief 打印二叉树
 *
 * @param t 要打印的二叉树
 */
void bitree_display_BST(PBiTree_t t) {
    if (t == NULL) {
        return;
    }

    if (t->left_child) {
        bitree_display_BST(t->left_child);
    }

    printf("%d\t", t->data);

    if (t->right_child) {
        bitree_display_BST(t->right_child);
    }
}